﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 1010.

How many numbers below a googol (10100) are not bouncy?

     * */
    class Problem113 : IProblem
    {
        public string Calculate()
        {
            //long n = 0;

            //long count = 0;

            //while (n < 999)
            //{
            //    n++;
            //    long tempI = n;

            //    bool ascending = false;
            //    bool descending = false;
            //    bool same = true;

            //    long previous = tempI % 10;
            //    tempI /= 10;
            //    while (tempI > 0)
            //    {
            //        long current = tempI % 10;

            //        if (previous > current)
            //        {
            //            ascending = true;
            //            same = false;
            //        }
            //        if (previous < current)
            //        {
            //            same = false;
            //            descending = true;
            //        }

            //        if (ascending && descending)
            //            break;

            //        previous = current;
            //        tempI /= 10;
            //    }

            //    bool bouncing = ascending && descending;
            //    if ((!ascending && descending) || same)
            //    {
            //        Console.WriteLine(n);
            //        count++;
            //    }
            //}

            //Console.WriteLine("Descending test: {0}", count);


            int digits = 99;

            long ascendingSum = Precalc(digits) - 1;
            long descendingSum = 0;

            for (int j = digits; j >= 1; j--)
            {
                descendingSum += Precalc(j) - 10;
            }

            //Console.WriteLine("Descending: {0}", descendingSum);


            long sum = ascendingSum + descendingSum;

            return sum.ToString();
        }

        long Precalc(int nDigits)
        {
            long[] precalc = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

            for (int j = 0; j < nDigits; j++)
                for (int i = 0; i < 9; i++)
                {
                    precalc[i] = precalc.Where((x, ind) => ind >= i).Sum();
                }

            return precalc.Sum();
        }
    }
}
